Most users tend to store various types of documents, including documents that contain private and sensitive information, in remote data servers. Such data servers are typically managed and owned by an external entity. While contractual obligations would compel the external entity to take security measures to ensure that no unauthorized access of documents stored within the data servers occur, there may be little that prevents the external entity itself from accessing the sensitive information contained within these documents should they wish to do so. Further, although the external entity would have taken security measures to prevent unauthorized access to documents stored within the data servers, security breaches may still inadvertently occur resulting in access to the documents being granted accidentally.
This problem may be addressed by encrypting the information contained within the documents and storing the documents in the data servers in an encrypted format. By doing so, the owner of the document would be the only person who would be able to access the information contained within the documents as the user would be the only one who would possess the secret key to decrypt the document. A common way to encrypt data is to use strong encryption methods such as the Advanced Encryption Standard (AES). AES is a standard of electronic encryption of data that utilizes symmetric keys to encrypt data. AES functions as follows. Data in a plaintext or clear text format is first inserted into a database. A user then uses a secret key to encrypt data in the database into a ciphertext. To retrieve the data, the user obtains the cipher-text from the database. The user then uses his secret key to decrypt the cipher-text to produce the original text.
The downside of this approach is that the user is prevented from carrying out any remote operations on the encrypted documents. For example, if the user wanted to carry out a remote search of the encrypted documents for specific data, the user would have to download all the documents into their local device, decrypt all the documents, and then carry out the search using the decrypted documents for the specific data. This methodology would only be useful if a small number of documents were to be searched. If the user is required to download a large number of documents to their local device before these documents may be decrypted and searched, this would run counter to the user's original motivation for storing a large number of documents in a remote data server. Ideally, the search should be carried out at the remote server whereby encrypted documents stored on the remote server are searched, and only the relevant encrypted documents and/or pages are returned to the user. This would mean that the user only needs to download encrypted documents and/or pages that contain the queried information and in spite of carrying out the searches at the remote server, the administrator of the remote server would not be aware of the queried information or the information contained within the downloaded data. Although there are many challenges in searching large volumes of encrypted documents for specific data, the encryption of documents or the information contained therein is widely recognized as an optimal method for protecting data at rest and for preventing the unauthorized access or theft of data. As such, those skilled in the art have come up with ways to search an encrypted database at a remote server for specific data without having to download the documents in an encrypted database to a local system before commencing the searching process.
A solution that has been developed to address the problem of searching large volumes of encrypted data for specific information is the Searchable Symmetric Encryption (SSE) solution. This solution utilizes a secure index that allows the user to search in real time for documents containing specified keywords. In short, a secure index allows users with a “trapdoor” for a “WORD” to test the index for only the “WORD”. During the search process, the secure index does not reveal any information about its contents. As the user is the only person who holds the secret key to generate trapdoors, the secure index safeguards the contents of the encrypted data from unauthorized access from unauthorized users. Most practical implementations of SSE only support the searching of documents for a single keyword. In such implementations, the remote server's work scales according to the size of the result set and the leakage to the server is limited to the set of encrypted documents that are returned and some global parameters of the system such as total data size and number of documents.
Another solution that has been proposed to address the problem of searching large encrypted databases utilizes secure two party protocols in which the remote server is provided with secure indices to encrypted documents and the client possesses a list of keywords to be queried. As the solution pre-computes parts of the protocol's messages and stores them in encrypted form in the remote server, the solution does away with multiple rounds of interactions between the remote server and the user. Due to the pre-computation that has taken place prior to the search, the user sends information to the server that allows the pre-computed information to be unlocked during a search without further interaction required between the user and the remote server. When the remote server is queried with the keywords, the remote server uses the secure indices to provide the user with encrypted pointers that point to documents that contain the queried keywords. The user then decrypts these pointers to obtain the documents that contain the required keywords. This solution is secure as the remote server is not unable to decrypt the pointers on its end nor can the remote server learn of the keywords in the client's query. However, these solutions do not allow for the searching of conjunctive keywords in a symmetrically encrypted database as they deal mostly with single keyword searches or multiple keyword searches.
For the above reasons, those skilled in the art are constantly striving to come up with a system and method that allows a user to search a symmetrically encrypted database for conjunctive keywords in a computationally efficient manner.